package com.lw.leetcode.bingChaJi.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 399. 除法求值
 * 剑指 Offer II 111. 计算除法
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/21 13:42
 */
public class CalcEquation {

    public static void main(String[] args) {
        CalcEquation test = new CalcEquation();

        List<List<String>> equations = new ArrayList<>();
        equations.add(Arrays.asList("a", "e"));
        equations.add(Arrays.asList("b", "e"));
        double[] values = {4, 3};
        List<List<String>> queries = new ArrayList<>();
        queries.add(Arrays.asList("b", "c"));
        queries.add(Arrays.asList("a", "c"));
        queries.add(Arrays.asList("a", "b"));
        queries.add(Arrays.asList("c", "b"));
        queries.add(Arrays.asList("b", "a"));
        queries.add(Arrays.asList("c", "a"));

        double[] doubles = test.calcEquation(equations, values, queries);
        System.out.println(Arrays.toString(doubles));

        System.out.println(test.map);
    }

    private Map<String, Node> map = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int size = equations.size();
        for (int i = 0; i < size; i++) {
            List<String> list = equations.get(i);
            String a = list.get(0);
            String b = list.get(1);
            Node an = find(a);
            Node bn = find(b);
            if (!an.next.equals(bn.next)) {
                map.put(bn.next, new Node(an.next, an.value * values[i] / bn.value));
            }
        }
        size = queries.size();
        double[] arr = new double[size];
        for (int i = 0; i < size; i++) {
            List<String> list = queries.get(i);
            String a = list.get(0);
            String b = list.get(1);
            Node an = find2(a);
            Node bn = find2(b);
            if (an == null || bn == null || !an.next.equals(bn.next)) {
                arr[i] = -1D;
                continue;
            }
            arr[i] = bn.value / an.value;
        }
        return arr;
    }

    private Node find(String key) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node(key, 1D);
            map.put(key, node);
            return node;
        }
        if (key.equals(node.next)) {
            return node;
        }
        Node no = find(node.next);
        map.put(key, new Node(no.next, no.value * node.value));
        return map.get(key);
    }

    private Node find2(String key) {
        Node node = map.get(key);
        if (node == null || key.equals(node.next)) {
            return node;
        }
        Node no = find(node.next);
        map.put(key, new Node(no.next, no.value * node.value));
        return map.get(key);
    }

    private static class Node {
        private String next;
        private double value;

        public Node(String next, double value) {
            this.next = next;
            this.value = value;
        }
    }

}
